package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-25 17:36
 */
public class BC213打家劫舍II2 {

    public static void main(String[] args) {
        int[] nums = {1, 1, 3, 6, 7, 10, 7, 1, 8, 5, 9, 1, 4, 4, 3};
        System.out.println(rob(nums));
    }

    /**
     * 首端与末端不能相连则分两种情况分别求出最优解 再比较最大值即可
     *
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }
        if(nums.length == 2){
            return Math.max(nums[0],nums[1]);
        }
        return Math.max(robWithOutFirst(nums),robWithOutEnd(nums));
    }

    /**
     * 不经过第一个房屋
     * @param nums
     * @return
     */
    public static int robWithOutFirst(int[] nums) {
        int one = 0;
        int two = nums[1];

        for (int i = 3; i <=nums.length; i++) {
            int next = Math.max(one+nums[i-1],two);
            one = two;
            two = next;
        }
        return two;
    }

    /**
     * 不经过最后一个房屋
     * @param nums
     * @return
     */
    public static int robWithOutEnd(int[] nums) {
        int one = nums[0];
        int two = Math.max(nums[0],nums[1]);

        for (int i = 3; i <nums.length; i++) {
            int next = Math.max(one+nums[i-1],two);
            one = two;
            two = next;
        }
        return two;
    }
}
